class MyCircularDeque
{
public:
    MyCircularDeque(int k)
    {
        this->_capacity = k;
        this->_size = 0;
        this->head = new DoubleLinkedList();
        this->tail = new DoubleLinkedList();
        this->head->next = tail;
        this->tail->pre = head;
    }

    bool insertFront(int value)
    {
        if (isFull())
        {
            return false;
        }
        else
        {
            DoubleLinkedList *newNode = new DoubleLinkedList();
            newNode->val = value;
            newNode->next = this->head->next;
            newNode->pre = this->head;
            this->head->next->pre = newNode;
            this->head->next = newNode;
            this->_size += 1;
            return true;
        }
    }

    bool insertLast(int value)
    {
        if (isFull())
        {
            return false;
        }
        else
        {
            DoubleLinkedList *newNode = new DoubleLinkedList();
            newNode->val = value;
            newNode->next = this->tail;
            newNode->pre = this->tail->pre;
            this->tail->pre->next = newNode;
            this->tail->pre = newNode;
            this->_size += 1;
            return true;
        }
    }

    bool deleteFront()
    {
        if (isEmpty())
        {
            return false;
        }
        else
        {
            DoubleLinkedList *toDel = this->head->next;
            this->head->next = this->head->next->next;
            this->head->next->pre = this->head;
            delete toDel;
            this->_size -= 1;
            return true;
        }
    }

    bool deleteLast()
    {
        if (isEmpty())
        {
            return false;
        }
        else
        {
            DoubleLinkedList *toDel = this->tail->pre;
            this->tail->pre = this->tail->pre->pre;
            this->tail->pre->next = this->tail;
            delete toDel;
            this->_size -= 1;
            return true;
        }
    }

    int getFront()
    {
        if (isEmpty())
        {
            return -1;
        }
        else
        {
            return this->head->next->val;
        }
    }

    int getRear()
    {
        if (isEmpty())
        {
            return -1;
        }
        else
        {
            return this->tail->pre->val;
        }
    }

    bool isEmpty()
    {
        return this->_size == 0;
    }

    bool isFull()
    {
        return this->_size == this->_capacity;
    }

private:
    class DoubleLinkedList
    {
    public:
        int val;
        DoubleLinkedList *pre;
        DoubleLinkedList *next;
    };

    int _capacity;
    DoubleLinkedList *head;
    DoubleLinkedList *tail;
    int _size;
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */